package com.kk.demo.unsface.two.unsafeList2;

import java.lang.reflect.Field;

import com.kk.demo.unsface.two.unsafelist.UnsafeHelper;

import sun.misc.Unsafe;

/**
 * Desc:
 * <p/>Date: 2016/11/27
 * <br/>Time: 18:05
 * <br/>User: gaozhiwen
 */
public class UnsafeArrayList<T> {
    private final long base;
    private final long elementSize;
    private final long firstFieldOffset;
    private Class<T> type;
    private int size;
    private static Unsafe unsafe = UnsafeHelper.getUnsafe();

    public UnsafeArrayList(int size, Class<T> t) {
        this.size = size;
        this.type = t;
        this.firstFieldOffset = UnsafeHelper.firstFieldOffset(t);
        this.elementSize = UnsafeHelper.sizeOf(type) - firstFieldOffset;
        this.base = unsafe.allocateMemory(elementSize * size);
    }

    public int size() {
        return size;
    }

    private long getAddress(int index) {
        return base + (index * elementSize);
    }

    public void add(int index, T t) {
        checkScale(index);
        unsafe.copyMemory(null, UnsafeUtil.getAddress(t) + firstFieldOffset, null, getAddress(index), elementSize);
    }

    public T get(int index) {
        checkScale(index);
        try {
            T t = (T) unsafe.allocateInstance(type);
            return get(index, t);
        } catch (InstantiationException e) {
            throw new RuntimeException("exception at allocate instance for type:" + type);
        }
    }

    private T get(int index, T t) {
        unsafe.copyMemory(null, getAddress(index), null, UnsafeUtil.getAddress(t) + firstFieldOffset, elementSize);
        return t;
    }

    private void checkScale(int index) {
        if (index > size - 1 || index < 0) {
            throw new RuntimeException("out of array index");
        }
    }

    public void sort(String filed) {
        long tmpBase = unsafe.allocateMemory(elementSize);
        try {
            Field field = type.getDeclaredField(filed);
            long pos = unsafe.objectFieldOffset(field) - firstFieldOffset;

            sort(tmpBase, 0, size - 1, pos);
        } catch (NoSuchFieldException e) {
            throw new RuntimeException("no such filed:" + filed);
        } finally {
            unsafe.freeMemory(tmpBase);
        }
    }

    private void sort(long tmpBase, int left, int right, long pos) {
        if (left >= right) {
            return;
        }

        unsafe.copyMemory(base + elementSize * left, tmpBase, elementSize);
        int baseId = unsafe.getInt(tmpBase);
        int baseValue = unsafe.getInt(tmpBase + pos);// 基数值，放入base

        int low = left;
        int high = right;

        while (low < high) {
            // 从右往左扫描，选择比基数小的数
            while (low < high) {
                int highId = unsafe.getInt(base + elementSize * high);
                int highValue = unsafe.getInt(base + elementSize * high + pos);
                if (highValue < baseValue || (highValue == baseValue && highId < baseId)) {
                    break;
                }
                high--;
            }
            if (low < high) {
                unsafe.copyMemory(base + elementSize * high, base + elementSize * low, elementSize);
            }

            // 从左往右扫描，选择比基数大的数
            while (low < high) {
                int lowId = unsafe.getInt(base + elementSize * low);
                int lowValue = unsafe.getInt(base + elementSize * low + pos);
                if (lowValue > baseValue || (lowValue == baseValue && lowId > baseId)) {
                    break;
                }
                low++;
            }
            if (low < high) {
                unsafe.copyMemory(base + elementSize * low, base + elementSize * high, elementSize);
            }
        }

        // 遍历完毕后将base放入low=high的位置
        unsafe.copyMemory(tmpBase, base + elementSize * low, elementSize);

        // 遍历拆分的两组数组
        sort(tmpBase, left, low - 1, pos);
        sort(tmpBase, low + 1, right, pos);
    }
}